package com.azure.code.graph.kruskal;

import com.azure.code.graph.unionFind.UF;

import java.util.Arrays;

/**
 *
 * 最低成本联通所有的城市
 *
 * 案例：
 *   输入N = 3， connections = [{1,2,5},{1,3,6},{2,3,1}]
 *   https://www.wenjiangs.com/doc/fdlaclqa
 */
public class Kruska_1135 {

    int minimumCost(int n, int[][] connections){
        // 城市编号1...n 所以初始化大小为n+1
        UF uf = new UF(n+1);
        // 对所有边的权重安装从小到大排序
        Arrays.sort(connections,(a,b)->(a[2]-b[2]));
        // 记录最小生成树的权重之和
        int mst = 0;
        for (int[] edge : connections) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            // 若这条边产生环，则不能加入mst
            if(uf.connect(u,v)){
                continue;
            }
            // 若这条边不会产生环，则输入最小生成树
            mst += weight;
            uf.union(u,v);
        }
        // 保证所有的节点都被连通
        // 按理说uf.count() == 1 说明所有的节点被连通
        // 但因为节点0 没有被使用，所以0 会额外占用一个连通分量
        return uf.count()==2? mst : -1;
    }
}
